package com.xk._02算法篇._02unionFind;

import com.xk._02算法篇._02unionFind.union.*;
import com.xk.tools.Asserts;
import com.xk.tools.Times;

/**
 * @description:
 * @author: xu
 * @date: 2022/10/4 19:49
 */
public class Main {
    private static final int COUNT = 5000000;

    public static void main(String[] args) {
       //test(new UnionFind_QF(12));
       //test(new UnionFind_QU(12));
       //test(new UnionFind_QU_Size(12));
       //test(new UnionFind_QU_Rank(12));
       //test(new UnionFind_QU_R_PC(12));
       //test(new UnionFind_QU_R_PS(12));
       //test(new UnionFind_QU_R_PH(12));

        /*Times.test("QF", new Times.Task() {
            @Override
            public void execute() {
                testTime(new UnionFind_QF(COUNT));
            }
        });

        Times.test("QU", new Times.Task() {
            @Override
            public void execute() {
                testTime(new UnionFind_QU(COUNT));
            }
        });*/
         //testTime(new UnionFind_QF(COUNT));
         //testTime(new UnionFind_QU(COUNT));
         testTime(new UnionFind_QU_Size(COUNT));
         testTime(new UnionFind_QU_Rank(COUNT));
         testTime(new UnionFind_QU_R_PC(COUNT));
         testTime(new UnionFind_QU_R_PS(COUNT));
         testTime(new UnionFind_QU_R_PH(COUNT));
         testTime(new GenericUnionFind<Integer>());
    }

    static void test(UnionFind uf){
        uf.union(0, 1);
        uf.union(0, 3);
        uf.union(0, 4);
        uf.union(2, 3);
        uf.union(2, 5);

        uf.union(6, 7);

        uf.union(8, 10);
        uf.union(9, 10);
        uf.union(9, 11);

        Asserts.test(!uf.isSame(2, 7));

        uf.union(4, 6);

        Asserts.test(uf.isSame(2, 7));
    }

    static void testTime(UnionFind uf) {
        Times.test(uf.getClass().getSimpleName(), new Times.Task() {
            @Override
            public void execute() {
                for (int i = 0; i < COUNT; i++) {
                    uf.union((int) (Math.random() * COUNT), (int) (Math.random() * COUNT));
                }
                for (int i = 0; i < COUNT; i++) {
                    uf.isSame((int) (Math.random() * COUNT), (int) (Math.random() * COUNT));
                }
            }
        });
    }

    static void testTime(GenericUnionFind<Integer> uf) {
        for (int i = 0; i < COUNT; i++) {
            uf.makeSet(i);
        }

        Times.test(uf.getClass().getSimpleName(), new Times.Task() {
            @Override
            public void execute() {
                for (int i = 0; i < COUNT; i++) {
                    uf.union((int) (Math.random() * COUNT), (int) (Math.random() * COUNT));
                }
                for (int i = 0; i < COUNT; i++) {
                    uf.isSame((int) (Math.random() * COUNT), (int) (Math.random() * COUNT));
                }
            }
        });
    }


    static void testUnionFind_QU(){
        UnionFind uf = new UnionFind_QU_Size(12);
        uf.union(0, 1);
        uf.union(0, 3);
        uf.union(0, 4);
        uf.union(2, 3);
        uf.union(2, 5);

        uf.union(6, 7);

        uf.union(8, 10);
        uf.union(9, 10);
        uf.union(9, 11);

        System.out.println(uf.isSame(2, 7));
        System.out.println(uf.isSame(0, 6));
        System.out.println(uf.isSame(0, 5));

        uf.union(4, 6);
        System.out.println(uf.isSame(2, 7));
        System.out.println(uf.isSame(0, 6));
    }

    static void testUnionFind_QF(){
        UnionFind uf = new UnionFind_QF(12);
        uf.union(0, 1);
        uf.union(0, 3);
        uf.union(0, 4);
        uf.union(2, 3);
        uf.union(2, 5);

        uf.union(6, 7);

        uf.union(8, 10);
        uf.union(9, 10);
        uf.union(9, 11);

        System.out.println(uf.isSame(0, 6));
        System.out.println(uf.isSame(0, 5));

        uf.union(4, 6);
        System.out.println(uf.isSame(0, 6));
        System.out.println(uf.isSame(2, 7));
    }
}
